package com.mj.listen3.排序_数组;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */
public class _51_数组中的逆序对 {
    // 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
    // 输入: [7,5,6,4]
    // 输出: 5
    public static void main(String[] args) {
        int[] arr = new int[]{7,5,6,4};
        System.out.println(reversePairs(arr));
    }

    public static int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] temp = new int[len];
        return mergeSort(nums, 0, len, temp);
    }

    /**
     * 对 [l, r) 范围内的数据进行归并排序; 左闭右开
     *
     * @param l
     * @param r
     */
    public static int mergeSort(int[] arr, int l, int r, int[] temp) {
        if (r - l < 2) return 0;// 至少要2个元素
        int mid = (r + l) >> 1;
        return mergeSort(arr, l, mid, temp) + mergeSort(arr, mid, r, temp) + merge(arr, l, mid, r, temp);
    }

    /**
     * 对将 [l, m) 和 [m, r) 范围的有序序列合并成一个有序序列
     *
     * @param l
     * @param mid
     * @param r
     */
    public static int merge(int[] nums, int l, int mid, int r, int[] temp) {
        for (int i = l; i < r; i++) {
            temp[i] = nums[i];
        }

        int i = l;
        int j = mid;

        int count = 0;
        for (int k = l; k < r; k++) {
            if (i == mid) {
                nums[k] = temp[j++];
            } else if (j == r) {
                nums[k] = temp[i++];
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i++];
            } else {
                nums[k] = temp[j++];
                count += (mid - i);
            }
        }
        return count;
    }
}
